package com.zwy.leetcode;

import java.util.*;

public class TreeTest {

    public static void main(String[] args) {
        TreeTest test=new TreeTest();
        int []nums=new int[]{
                1,2,3,0,0,0
        };
        int []nums2=new int[]{
                2,5,6
        };
        int m=3,n=3;
        test.merge(nums,m,nums2,n);
    }

    /**
     * 二叉树的最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        Stack<TreeNode>stack=new Stack<>();
        stack.push(root);
        TreeNode p;
        int depth=0;
        if(root==null)return 0;
        while(!stack.isEmpty()){
            if(depth<stack.size())depth=stack.size();
            if(stack.peek().left!=null){
                 p=stack.peek();
                stack.push(stack.peek().left);
                p.left=null;
                continue;
            }
            if(stack.peek().right!=null){
                 p=stack.peek();
               stack.push(stack.peek().right);
                p.right=null;
               continue;
            }
            if(stack.peek().left==null&&stack.peek().right==null)stack.pop();

        }
        return depth;
    }

    /**
     * 验证二叉搜索树
     * @param root
     * @return
     */

        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }

        public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
            if (root == null)
                return true;
            //每个节点如果超过这个范围，直接返回false
            if (root.val >= maxVal || root.val <= minVal)
                return false;
            //这里再分别以左右两个子节点分别判断，
            //左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
            //右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
            return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
        }


    /**
     * 对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
            if(root==null)return true;

        return isSymmetricHelp(root.left,root.right);
    }
    public boolean isSymmetricHelp(TreeNode left,TreeNode right){
        if (left == null && right == null)
            return true;
        //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == null || right == null || left.val != right.val)
            return false;
        return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
    }

    /**
     *二叉树的层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode>queue=new LinkedList<TreeNode>();
        List<List<Integer>>lists=new ArrayList<List<Integer>>();
        List<Integer>list=new ArrayList<>();
        if (root==null)return lists;
        list.add(root.val);
        lists.add(list);
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer>list1=new ArrayList<Integer>();

            int count=queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode p=queue.peek();
                if(p.left!=null){
                    queue.offer(p.left);
                    list1.add((p.left.val));
                }
                if(p.right!=null){
                    queue.offer(p.right);
                    list1.add((p.right.val));
                }
                queue.poll();
            }
            if(list1.size()>0)lists.add(list1);
        }
        return lists;
    }

    /**
     * 将有序数组转换为二叉搜索树
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root=new TreeNode();
        int length=nums.length;
        if(length==1){
            root.val=nums[0];
            return root;
        }
        int mid=0;
        mid=length/2+1;
        int leftNum=length/2;
        int rightNum=length%2==0?leftNum-1:leftNum;
        int []left=new int[leftNum];
        int []right=new int[rightNum];
        for (int i = 0; i < leftNum; i++) {
            left[i]=nums[i];
        }
        for (int i = 0; i < rightNum; i++) {
            right[i]=nums[mid+i];
        }
        root.val=nums[mid-1];
        if(leftNum>0)root.left=sortedArrayToBST(left);
        if(rightNum>0)root.right=sortedArrayToBST(right);
        return root;
    }

    /**
     * 合并两个有序数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m; i < nums1.length; i++) {
            nums1[i]=nums2[i-m];
        }
        for (int i = 0; i < nums1.length - 1; i++) {
            for (int j = 0; j < nums1.length - i -1; j++) {   // 这里说明为什么需要-1
                if (nums1[j] > nums1[j + 1]) {
                    int temp = nums1[j];
                    nums1[j] = nums1[j + 1];
                    nums1[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 第一个错误的版本
     * @param n
     * @return
     */
    public int firstBadVersion(int n) {
       return 0;
    }

    /**
     * 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 1)
            return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //买卖股票的最佳时机
    public int maxProfit(int[] prices) {

        return 0;
    }


}
